﻿//Copyright (c) 2010 Christopher E. S. King (http://chriskingconsulting.com)
//
//Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files 
// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, 
// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do 
// so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE 
// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

// enumerate IList
// traverse using Stack<T>; null out frames for async traversal
// ancestory non-object traversal; HasAncestor()

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Collections;
using System.Collections.Concurrent;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.Reflection;
using System.Text;
using System.Dynamic;
using System.Xml.Linq;

using King.Extensions;
using King.Reflection;
using King.Text;
using King.Collections;

namespace King.Traverse {

    public abstract class Info {

        protected internal static readonly object NullResult = new object();

        internal static readonly Info Dummy = new DummyInfo();
        private class DummyInfo : Info {
            public override string ToString(Value value) {
                return "(dummy root node)";
            }
            public override bool IsInternalNode(Value value) {
                return true;
            }
            public override Value Children(Context context) {
                return context.Value;
            }
        }

        public virtual string ToString(Value value) {
            return value.Object.ToString();
        }

        public virtual void InitializeFrame(Context context) {
        }
        public virtual void DeinitializeFrame(Context context) {
        }

        public virtual bool IsInternalNode(Value value) { 
            return false;
        }
        public virtual bool EnumerateForChildren {
            get { return false; }
        }
        public virtual Value Children(Context context) {
            return default(Value);
        }

        public virtual bool UsePhysicalStack { 
            get { return false; } 
        }
        public virtual bool ImplementsSubstitute {
            get { return false; }
        }
        public virtual bool IsSubstituteType(Type type) {
            return false;
        }

        public virtual Type[] AuxiliaryStacks() {
            return Type.EmptyTypes;
        }

        public virtual bool Prolog(Context context, Value value, out Value substitute) {
            substitute = default(Value);
            return false;
        }
        public virtual bool Substitute(Context context, Value value, out Value substitute) {
            substitute = default(Value);
            return false;
        }
        public virtual void Epilog(Context context, Value value) {
        }
        public virtual bool Result(Context context, Value value, out Value substitute) {
            substitute = default(Value);
            return false;
        }
    }
    public abstract class Evaluation<T> where T : Info {

        // begin directed evaluation!
        public static IEnumerable<Value> Evaluate(object value,
            Context? maybeParentContext = null,
            bool isAsynchronous = false) {

            // get parent evaluation from parent context
            Evaluation parentEvaluation = null;
            if (maybeParentContext != null) {
                var parentContext = maybeParentContext.Value;

                // check that context is initialized
                if (parentContext.Type == Context.Scope.InitializeFrame)
                    throw new InvalidOperationException();

                parentEvaluation = parentContext.Evaluation;
            }

            // activate evaluator
            return new Evaluator(Loader.GetLoader(typeof(T)), 
                new Value(value),
                parentEvaluation,
                isAsynchronous: isAsynchronous);
        }
    }

    public struct Value {
        private object m_object;
        private char? m_character;

        public Value(object value) {
            Contract.Assert(!(value is Value));

            // Value unboxes itself
            while (value is Value)
                value = ((Value)value).Object;

            m_character = null;
            m_object = null;

            var character = value as char?;
            if (character != null)
                m_character = character;
            else
                m_object = value;
        }
        public Value(char? character) {
            m_object = null;
            m_character = character;
        }

        public bool IsNull {
            get { return m_object == null && m_character == null; }
        }
        public Type Type {
            get {
                if (m_character != null)
                    return typeof(char);
                if (m_object != null)
                    return m_object.GetType();
                return null;
            }
        }
        public object Object {
            get {
                if (m_character != null)
                    return m_character;

                return m_object; 
            }
        }
        public bool IsReference {
            get { return m_object != null; }
        }

        public char? AsCharacter {
            get { return m_character; }
        }
        public char? Character {
            get {
                if (m_object != null)
                    throw new InvalidCastException();
                return AsCharacter; 
            }
        }
        public bool IsCharacter {
            get { return Type == typeof(char); }
        }

        public override string ToString() {
            if (IsNull)
                return null;

            return Object.ToString();
        }
    }
    public partial struct Context {

        public partial struct Enumerator : IEnumerable<Context>, IEnumerator<Context> {

            private readonly Evaluation m_evaulation;
            private readonly Type m_type;
            private LinkEnumerator<Frame> m_enumerator;

            internal Enumerator(LinkEnumerator<Frame> enumerator,
                Evaluation evaluation, Type type) {

                m_evaulation = evaluation;
                m_type = type;
                m_enumerator = enumerator;
            }

            // IEnumerable<Context> (see boilerplate)
            public Context Current {
                get {
                    var scope = Scope.Initialized;
                    return new Context(m_evaulation, m_enumerator.Current, scope);
                }
            }
            public bool MoveNext() {
                while (m_enumerator.MoveNext()) {

                    // no type filter
                    if (m_type == null)
                        return true;

                    // filter by type
                    var type = m_enumerator.Current.Node.Type;

                    // test if the types equal
                    if (type == m_type)
                        return true;

                    // test if type is a subclass of m_type
                    if (!m_type.IsSealed && m_type.IsAssignableFrom(type))
                        return true;
                }

                return false;
            }

            // IEnumerator<Context> (see boilerplate)
            public Enumerator GetEnumerator() {
                return new Enumerator(m_enumerator.GetEnumerator(), m_evaulation, m_type);
            }
        }
        public struct Continuation : IEnumerable<Value> {
            private IEnumerator<Value> m_enumerator;
            private bool m_used;

            public Continuation(IEnumerator<Value> enumerator) {
                m_enumerator = enumerator;
                m_used = false;
            }

            public IEnumerator<Value> GetEnumerator() {
                if (m_used)
                    throw new InvalidOperationException();
                return m_enumerator;
            }
            IEnumerator IEnumerable.GetEnumerator() {
                return GetEnumerator();
            }
        }

        internal enum Scope {
            Initialized,
            InitializeFrame,
            PrologEpilogResult,
            Substitute,
        }

        private Scope m_scope;
        private Frame m_frame;
        private Evaluation m_evaluation;

        internal Context(Evaluation evaluation, Frame frame, Scope scope) {
            m_scope = scope;
            m_frame = frame;
            m_evaluation = evaluation;
        }
        
        // identity
        internal Evaluation Evaluation {
            get { return m_evaluation; }
        }
        internal Scope Type {
            get { return m_scope; }
        }
        
        // loader
        private Loader Loader {
            get { return m_evaluation.Loader; }
        }
        public Type InfoType {
            get { return Loader.InfoType; }
        }

        // value
        public Value Value {
            get { return m_frame.Node.Value; }
        }
        public object Object {
            get { return Value.Object; }
        }
        public bool IsNull {
            get { return m_frame == null; }
        }

        // substitution
        public bool Substitute(Value value, out Value substitute) {
            substitute = default(Value);

            if (value.IsNull)
                return false;

            // skip current frame when called from within substitute 
            var frame = m_frame;
            if (m_scope == Scope.Substitute)
                frame = frame.Parent;

            // try substitute
            var node = new Node(Loader, value);
            if (!frame.Substitute(m_evaluation, node, out substitute))
                return false;

            return true;
        }

        // continuation
        public Continuation Continue(Value value) {
            var continuation = m_frame.Continue(m_evaluation, value);
            return new Continuation(continuation);
        }

        // local
        public object Local {
            get { return m_frame.GetLocal(m_evaluation); }
            set {
                if (m_scope == Scope.PrologEpilogResult)
                    throw new InvalidOperationException(
                        "State cannot be set in a prolog, epilog, or result transform" +
                        " as the frame is not yet/no longer on the stack.");

                m_frame.SetLocal(m_evaluation, value); 
            }
        }

        // ancestors
        public Enumerator Ancestors(Type filter = null, Type auxiliary = null, bool includeSelf = false) {

            // enumerate frames starting with the first frame deeper frame
            IStackable<Frame> frame = m_frame;
            if (auxiliary != null)
                 frame = m_evaluation.TryGetTopOfAuxiliaryStack(auxiliary);

            // skip this frame unless in a prolog 
            if (m_scope != Scope.PrologEpilogResult) {

                // skip private frames deeper than the current frame
                while (frame != null) {
                    if (includeSelf && frame.Depth > m_frame.Depth)
                        frame = frame.Next;

                    else if (!includeSelf && frame.Depth >= m_frame.Depth)
                        frame = frame.Next;

                    else break;
                }
            }

            // wrap a link enumerator to contexts and filtering by type
            var linkEnumerator = new LinkEnumerator<Frame>(frame);
            return new Enumerator(linkEnumerator, m_evaluation, filter);
        }

        // initialize frame
        public void ContinueSubstitutionAfter(Context context) {
            if (context.Equals(default(Context)))
                throw new ArgumentNullException();

            if (m_scope != Scope.InitializeFrame)
                throw new InvalidOperationException();

            m_frame.ContinueSubstitutionAt(context.m_frame.Parent);
        }
        public void ContinueSubstitutionAt(Context context) {
            if (context.Equals(default(Context)))
                throw new ArgumentNullException();

            if (m_scope != Scope.InitializeFrame)
                throw new InvalidOperationException();

            m_frame.ContinueSubstitutionAt(context.m_frame);
        }
        public void SuppressSubstitute() {
            if (m_scope != Scope.InitializeFrame)
                throw new InvalidOperationException();

            m_frame.SuppressSubstitute();
        }
    }

    internal sealed class Loader {
        internal const int DefaultRecyclerCapacity = 8;

        internal static Loader GetLoader(Type infoType) {
            Loader loader;

            lock (s_loaders)
                if (s_loaders.TryGetValue(infoType, out loader))
                    return loader;

            loader = new Loader(infoType);

            lock (s_loaders)
                s_loaders[infoType] = loader;

            return loader;
        }

        static Loader() {
            s_loaders = new Dictionary<Type, Loader>();
        }

        private static readonly object LoaderLock = new object();
        private static Dictionary<Type, Loader> s_loaders;

        private Type m_infoType;
        private Dictionary<Type, Info> m_infosByType;

        // multi-threaded info cache
        internal Loader(Type infoType) {
            m_infoType = infoType;
            m_infosByType = new Dictionary<Type, Info>();
        }

        internal Info GetInfo(Type type) {
            Info info;
            lock (LoaderLock) {
                if (m_infosByType.TryGetValue(type, out info))
                    return info;
            }

            info = (Info)m_infoType.Activate(type);

            lock (LoaderLock)
                m_infosByType[type] = info;

            return info;
        }
        internal Type InfoType {
            get { return m_infoType; }
        }
    }
    internal struct Node {

        internal static Node GetDummyNode(Value root) {
            return new Node {
                m_value = root,
                m_info = Info.Dummy
            };
        }

        private Value m_value;
        private Info m_info;

        internal Node(Loader loader, Value value) {
            m_info = loader.GetInfo(value.Type);
            m_value = value;
        }

        internal Type Type {
            get { return m_value.Type; }
        }
        internal Info Info {
            get { return m_info; }
        }
        internal Value Value {
            get { return m_value; }
        }
        internal object Object {
            get { return Value.Object; }
        }
        internal bool IsDummy {
            get { return m_info == Info.Dummy; }
        }

        internal void InitializeFrame(Context context) {
            m_info.InitializeFrame(context);
        }
        internal void DeinitializeFrame(Context context) {
            m_info.DeinitializeFrame(context);
        }

        internal bool IsInternalNode {
            get { return m_info.IsInternalNode(m_value); }
        }
        internal Value Children(Context context) {
            if (m_info.EnumerateForChildren)
                return m_value;
            return m_info.Children(context);
        }
        public bool EnumerateForChildren {
            get { return m_info.EnumerateForChildren; }
        }
        
        internal bool ImplementsSubstitute {
            get { return m_info.ImplementsSubstitute; }
        }
        internal bool UsePhysicalStack {
            get { return m_info.UsePhysicalStack; }
        }
        internal bool IsSubstituteType(Type type) {
            return m_info.IsSubstituteType(type);
        }
        internal IEnumerable<Type> AuxiliaryStacks() {
            return m_info.AuxiliaryStacks();
        }

        internal bool Prolog(Context context, out Value substitute) {
            return m_info.Prolog(context, m_value, out substitute);
        }
        internal bool Substitute(Context context, Value value, out Value substitute) {
            return m_info.Substitute(context, value, out substitute);
        }
        internal void Epilog(Context context) {
            m_info.Epilog(context, m_value);
        }
        internal bool Result(Context context, Value result, out Value substitute) {
            return m_info.Result(context, result, out substitute);
        }

        public override string ToString() {
            return m_info.ToString(m_value);
        }
    }

    internal struct ChildrenEnumerator {

        private delegate bool MoveNextDelegate(Value children, ref int index, ref Value current);

        private static void Initialize() {
            s_moveNextSingleton = MoveNextSingleton;
            s_moveNextString = MoveNextString;

            s_moveNextCharacterArray = MoveNextCharacterArray;
            s_moveNextNullableCharacterArray = MoveNextNullableCharacterArray;
            s_moveNextObjectArray = MoveNextObjectArray;

            s_moveNextCharacterList = MoveNextCharacterList;
            s_moveNextNullableCharacterList = MoveNextNullableCharacterList;
            s_moveNextIList = MoveNextIList;

            s_moveNextCharacterEnumerator = MoveNextCharacterEnumerator;
            s_moveNextNullableCharacterEnumerator = MoveNextNullableCharacterEnumerator;
            s_moveNextEnumerator = MoveNextEnumerator;
        }
        private static MoveNextDelegate InitializeMoveNextWithIndex(object children) {

            // string
            if (children is string)
                return s_moveNextString;

            // arrays
            if (children is object[]) {

                if (children is char[])
                    return s_moveNextCharacterArray;

                if (children is char?[])
                    return s_moveNextNullableCharacterArray;

                else
                    return s_moveNextObjectArray;
            }

            // lists
            if (children is IList) {

                if (children is List<char>)
                    return s_moveNextCharacterList;

                if (children is List<char?>)
                    return s_moveNextNullableCharacterList;

                return s_moveNextIList;
            }

            return null;
        }
        private static MoveNextDelegate InitializeMoveNextEnumerable(object children) {

            // initialize IEnumerator enumeration
            if (children is IEnumerable<char>)
                return s_moveNextCharacterEnumerator;

            if (children is IEnumerable<char?>)
                return s_moveNextNullableCharacterEnumerator;

            return s_moveNextEnumerator;
        }

        // todo dynamic methods
        #region Static Private MoveNext Implementations
        private static bool MoveNextSingleton(Value value, ref int index, ref Value current) {
            if (++index == 1)
                return false;
            current = value;
            return true;
        }
        private static bool MoveNextString(Value value, ref int index, ref Value current) {
            var children = (string)value.Object;
            if (++index == children.Length)
                return false;
            current = new Value(children[index]);
            return true;
        }
        private static bool MoveNextCharacterArray(Value value, ref int index, ref Value current) {
            var children = (char[])value.Object;
            if (++index == children.Length)
                return false;
            current = new Value(children[index]);
            return true;
        }
        private static bool MoveNextNullableCharacterArray(Value value, ref int index, ref Value current) {
            var children = (char?[])value.Object;
            if (++index == children.Length)
                return false;
            current = new Value(children[index]);
            return true;
        }
        private static bool MoveNextObjectArray(Value value, ref int index, ref Value current) {
            var children = (object[])value.Object;
            if (++index == children.Length)
                return false;
            current = new Value(children[index]);
            return true;
        }

        private static bool MoveNextCharacterList(Value value, ref int index, ref Value current) {
            var children = (List<char>)value.Object;
            if (++index == children.Count)
                return false;
            current = new Value(children[index]);
            return true;
        }
        private static bool MoveNextNullableCharacterList(Value value, ref int index, ref Value current) {
            var children = (List<char?>)value.Object;
            if (++index == children.Count)
                return false;
            current = new Value(children[index]);
            return true;
        }
        private static bool MoveNextIList(Value value, ref int index, ref Value current) {
            var children = (IList)value.Object;
            if (++index == children.Count)
                return false;
            current = new Value(children[index]);
            return true;
        }

        private static bool MoveNextCharacterEnumerator(Value value, ref int index, ref Value current) {
            var children = (IEnumerator<char>)value.Object;
            if (!children.MoveNext())
                return false;
            current = new Value(children.Current);
            return true;
        }
        private static bool MoveNextNullableCharacterEnumerator(Value value, ref int index, ref Value current) {
            var children = (IEnumerator<char?>)value.Object;
            if (!children.MoveNext())
                return false;
            current = new Value(children.Current);
            return true;
        }
        private static bool MoveNextEnumerator(Value value, ref int index, ref Value current) {
            var children = (IEnumerator)value.Object;
            if (!children.MoveNext())
                return false;
            current = new Value(children.Current);
            return true;
        }
        #endregion

        #region Private Static Delegates to MoveNext Implementations
        private static MoveNextDelegate s_moveNextSingleton;
        private static MoveNextDelegate s_moveNextString;

        private static MoveNextDelegate s_moveNextCharacterArray;
        private static MoveNextDelegate s_moveNextNullableCharacterArray;
        private static MoveNextDelegate s_moveNextObjectArray;

        private static MoveNextDelegate s_moveNextCharacterList;
        private static MoveNextDelegate s_moveNextNullableCharacterList;
        private static MoveNextDelegate s_moveNextIList;

        private static MoveNextDelegate s_moveNextCharacterEnumerator;
        private static MoveNextDelegate s_moveNextNullableCharacterEnumerator;
        private static MoveNextDelegate s_moveNextEnumerator;
        #endregion

        private Value m_children;
        private Value m_current;
        private MoveNextDelegate m_moveNext;
        private int m_index;

        internal ChildrenEnumerator(Node node) {

            m_index = -1;
            m_current = default(Value);
            m_children = node.Value;

            // initialize delegates
            if (s_moveNextEnumerator == null)
                Initialize();

            // singleton
            if (!node.IsInternalNode || !node.EnumerateForChildren) {
                m_moveNext = s_moveNextSingleton;

            } else {

                // children indexable
                m_moveNext = InitializeMoveNextWithIndex(node.Object);

                // must use enumerator
                if (m_moveNext == null) {
                    m_moveNext = InitializeMoveNextEnumerable(node.Object);
                    var enumerable = (IEnumerable)node.Object;
                    m_children = new Value(enumerable.GetEnumerator());
                }
            }
        }

        internal bool IsNull {
            get { return m_children.IsNull; }
        }
        internal Value Current {
            get { return m_current; }
        }
        internal bool MoveNext() {
            return m_moveNext(m_children, ref m_index, ref m_current);
        }
    }
    internal sealed partial class AuxiliaryFrame : IStackable<Frame>, IRecyclable {

        private AuxiliaryFrame m_parent;
        private Frame m_frame;
        private bool m_recyclable;

        public AuxiliaryFrame() {
            m_recyclable = true;
        }

        // Identity
        internal AuxiliaryFrame Parent {
            get { return m_parent; }
        }
        internal Frame Frame {
            get { return m_frame; }
        }

        // IEnumerator<Frame> (see boilerplate)
        internal LinkEnumerator<Frame> GetEnumerator() {
            return new LinkEnumerator<Frame>(this);
        }

        // ISoundable<Frame>
        IStackable<Frame> IStackable<Frame>.Next {
            get { return Parent; }
        }
        
        // ILinkable<Frame>
        Frame ILinkable<Frame>.Value {
            get { return m_frame; }
        }
        int IStackable<Frame>.Depth {
            get { return m_frame.Depth; }
        }
        ILinkable<Frame> ILinkable<Frame>.Next {
            get { return Parent; }
        }

        // IRecyclable
        public bool Recyclable {
            get { return m_recyclable; }
            set {
                Contract.Assert(value == false);
                m_recyclable = value; 
            }
        }
        void Initialize(Frame frame, AuxiliaryFrame parent) {
            Contract.Assert(Recyclable);
            m_parent = parent;
            m_frame = frame;
        }

        public override string ToString() {
            return m_frame.ToString();
        }
    }
    internal sealed partial class Frame : IEnumerator<Node>, IStackable<Frame>, IRecyclable {

        [DebuggerDisplay("{m_frame.ToString()}", 
            Name = "{m_frame.ToStringDebug()}",
            Type = "{m_frame.m_node.Type.FullName}")]
        internal class DebugFrame {
            private Frame m_frame;
            internal DebugFrame(Frame frame) {
                m_frame = frame;
            }
        }

        #region Private Data Members
        // identity
        private Evaluation m_evaluation;
        private Frame m_parent;
        private Node m_node;
        private int m_depth;

        // local (for m_evauation)
        private object m_local;
        private bool m_mayHaveLocals;

        // child enumeration
        private ChildrenEnumerator m_children;
        private int m__nextChildIndex;
        private Node m_currentChild;

        // state
        private bool m_frameInitialized;
        private bool m_implementsSubstitute;
        private bool m_recyclable;

        // substitution stacks
        private Frame m_nextSubstitute;
        private Frame m_nextLogicalSubstitute;
        #endregion

        private Loader Loader {
            get { return m_evaluation.Loader; }
        }
        private Frame Next {
            get {

                // skip dummy nodes
                if (Parent != null && Parent.Node.IsDummy)
                    return Parent.Parent;

                return Parent;
            }
        }

        // life cycle
        bool IRecyclable.Recyclable {
            get { return m_recyclable; }
        }
        internal void Initialize(Evaluation evaluation, Frame parent, Node node) {
            // identity
            m_evaluation = evaluation;
            m_parent = parent;
            m_node = node;
            m_depth = parent == null ? 0 : parent.m_depth + 1;

            // flags
            m_recyclable = false;
            m_local = null;
            m_frameInitialized = false;

            // children
            m_children = default(ChildrenEnumerator);
            m__nextChildIndex = 0;
            m_currentChild = default(Node);

            // substitute
            m_implementsSubstitute = node.ImplementsSubstitute;
            m_nextSubstitute = null;
            m_nextLogicalSubstitute = null;

            // local
            m_local = null;

            // initialize frame
            var context = new Context(m_evaluation, this, Context.Scope.InitializeFrame);
            m_node.InitializeFrame(context);

            if (parent != null) {

                // initialize next substitution                
                m_nextSubstitute = parent.m_implementsSubstitute ?
                    parent : parent.m_nextSubstitute;

                // initialize next logical substitution if FrameInitialization didn't
                if (m_nextLogicalSubstitute == null)
                    ContinueSubstitutionAt(parent);
            }

            m_frameInitialized = true;
        }
        internal void Deinitialize() {
            var context = new Context(m_evaluation, this, Context.Scope.Initialized);
            m_node.DeinitializeFrame(context);
        }

        // identity
        internal Evaluation Evaluation {
            get { return m_evaluation; }
        }
        internal Frame Parent {
            get { return m_parent; }
        }
        internal Node Node {
            get { return m_node; }
        }
        internal int Depth {
            get { return m_depth; }
        }

        // local
        internal object GetLocal(Evaluation evaluation) {

            var sameEvaluator = evaluation.Evaluator == m_evaluation.Evaluator;

            // if frame belongs to this evaluator...
            if (sameEvaluator) {
                
                // release local when popping this frame
                m_mayHaveLocals = true;

                // hit cache 
                if (m_local != null)
                    return m_local;
            }

            // try lookup local
            return evaluation.TryGetLocal(this);
        }
        internal void SetLocal(Evaluation evaluation, object value) {
            // cache local on evaluation
            evaluation.SetLocal(this, value);

            // if frame owned by this evaluator then cache local on frame 
            var sameEvaluator = evaluation.Evaluator == m_evaluation.Evaluator;
            if (sameEvaluator)
                m_local = value;
        }
        internal bool MayHaveLocals {
            get { return m_mayHaveLocals; }
        }

        // substitution
        internal bool Substitute(Evaluation evaluation, Node node, out Value substitute) {
            substitute = default(Value);

            if (evaluation == null)
                evaluation = Evaluation;

            // substitutes something
            if (m_implementsSubstitute && m_node.IsSubstituteType(node.Type)) {

                // substitute
                var context = new Context(evaluation, this, Context.Scope.Substitute);
                var substituted = m_node.Substitute(context, node.Value, out substitute);

                // substituion finished
                if (substituted)
                    return true;
            }

            // next ancestor that substitutes 
            var nextFrame = node.UsePhysicalStack ?
                m_nextSubstitute : // nodes shared across context (i.e. StartLines)
                m_nextLogicalSubstitute; // common case

            // no more ancestors
            if (nextFrame == null)
                return false;

            // ancestor substitution
            return nextFrame.Substitute(evaluation, node, out substitute);
        }
        internal void ContinueSubstitutionAt(Frame frame) {
            m_nextLogicalSubstitute =
                frame.m_implementsSubstitute || frame.m_node.IsDummy ?
                    frame : frame.m_nextLogicalSubstitute;
        }
        internal void SuppressSubstitute() {
            Contract.Assert(m_frameInitialized == false);

            if (m_implementsSubstitute == false)
                throw new InvalidOperationException();

            m_implementsSubstitute = false;
        }

        // ISoundable<Frame>, ILinkable<Frame>, IEnumerable<Frame> (see boilerplate)
        internal LinkEnumerator<Frame> GetEnumerator() {
            return new LinkEnumerator<Frame>(this);
        }

        // continuations
        internal Evaluation Continue(Evaluation evaluation, Value value) {
            return evaluation.Continue(value);
        }

        // IEnumerator<Node> (see boilerplate)
        public Node Current {
            get { return m_currentChild; }
        }
        public bool MoveNext() {

            // moving implicitly ends continuations
            m_evaluation.DisposeContinuation();

            // initialize children enumerator
            if (m_children.IsNull) {

                // get children enumerator
                var context = new Context(m_evaluation, this, Context.Scope.Initialized);
                var children = m_node.Children(context);
                    
                // no children
                if (children.IsNull)
                    return false;

                m_children = new ChildrenEnumerator(new Node(Loader, children));
            }

            // move to next non-null child
            while (m_children.MoveNext()) {

                // skip child if null
                var currentValue = m_children.Current;
                if (currentValue.IsNull)
                    continue;

                // get child
                var currentNode = new Node(Loader, currentValue);

                // try substitute child
                Value substitute;
                if (Substitute(m_evaluation, currentNode, out substitute)) {

                    // skip child if substitute null
                    if (substitute.IsNull)
                        continue;

                    // substitute child
                    currentNode = new Node(Loader, substitute);
                }

                // cache child or substitute
                m_currentChild = currentNode;
                m__nextChildIndex++;
                return true;
            }

            // no more children
            return false;
        }

        public override string ToString() {
            return m_node.ToString();
        }
    }

    [DebuggerDisplay(@"\{Type = {m_evaluator.Loader.InfoType.Name} TopOfStack = {m_topOfStack}}")]
    internal sealed partial class Evaluation : IEnumerator<Value> {

        internal class DebuggerEvaluationProxy {

            private const int MaxStackDisplayDepth = 30;

            private Evaluation m_evaluation;

            public DebuggerEvaluationProxy(Evaluation evaluation) {
                m_evaluation = evaluation;
            }

            [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
            public object[] Stack {
                get {
                    // get stack
                    var stack = m_evaluation.m_topOfStack
                        .ToLinkList(o => o.Parent)
                        .Select(o => new Frame.DebugFrame(o))
                        .Cast<object>();

                    // prepend current child of top-of-stack frame
                    var currentChild = m_evaluation.m_topOfStack._Current;
                    if (!currentChild.IsNull)
                        stack = new object[] {
                            currentChild.Object
                        }.Concat(stack);

                    // display a constant number of frames so VS won't collapse variable
                    stack = stack.Concat(new object[MaxStackDisplayDepth])
                        .Take(MaxStackDisplayDepth);

                    return stack.ToArray();
                }
            }
        }

        private readonly Evaluator m_evaluator;
        private readonly Value m_root;
        private readonly Frame m_bottomOfStack;
        private readonly bool m_isContinuation;

        private bool m_isDisposed;
        private Evaluation m_continuation;

        private Frame m_topOfStack;
        private IEnumerator<Value> m_traversal;
        private Dictionary<Type, AuxiliaryFrame> m_topOfAuxiliaryStacks;
        private Dictionary<Frame, object> m_localsByFrame;

        internal Evaluation(Evaluator evaluator) {
            m_evaluator = evaluator;
            m_root = evaluator.Root;
            m_bottomOfStack = evaluator.TopOfStack;

            Reset();
        }
        internal Evaluation(Evaluation evaluation, Value value) {
            // continuation constructor. A continuation behaves like an evaluation
            // except that it does not clone inherited frame locals. 

            m_root = value;
            m_isContinuation = true;

            // continue using data structures supplied by continued evaluation
            m_evaluator = evaluation.m_evaluator;
            m_bottomOfStack = evaluation.m_topOfStack;
            m_topOfAuxiliaryStacks = evaluation.m_topOfAuxiliaryStacks;
            m_localsByFrame = evaluation.m_localsByFrame;

            // continue
            m_traversal = Traverse().GetEnumerator();
        }

        internal Evaluator Evaluator {
            get { return m_evaluator; }
        }

        // auxiliary stacks
        private void PopAuxiliary(Type type) {

            // pop
            var topOfAuxiliaryStack = m_topOfAuxiliaryStacks[type];
            m_topOfAuxiliaryStacks[type] = topOfAuxiliaryStack.Parent;

            // recycle
            var recycler = GetRecycler<AuxiliaryFrame>();
            recycler.Recycle(topOfAuxiliaryStack);
        }
        private void PushAuxiliary(Type type) {

            // recycler
            var recycler = GetRecycler<AuxiliaryFrame>();

            // get top of auxiliary stack (null if no stack exists)
            var topOfAuxiliaryStack = TryGetTopOfAuxiliaryStack(type);

            // reuse/activate frame and link it to the parent
            topOfAuxiliaryStack = recycler.Reuse(m_topOfStack, topOfAuxiliaryStack);

            // push
            m_topOfAuxiliaryStacks[type] = topOfAuxiliaryStack;                
        }

        // stack
        private Frame NewFrame(Frame parent, Node node) {
            return m_evaluator.GetRecycler<Frame>().Reuse(this, parent, node);
        }
        private void Pop() {

            // the popped node
            var frame = m_topOfStack;
            var node = frame.Node;

            // dispose frame
            frame.Deinitialize();

            // pop auxiliary stacks
            var privateStacks = (Type[])node.AuxiliaryStacks();
            if (privateStacks != null) {
                for (int i = 0; i < privateStacks.Length; i++)
                    PopAuxiliary(privateStacks[i]);
            }

            // release local
            if (m_localsByFrame != null && m_topOfStack.MayHaveLocals)
                m_localsByFrame.Remove(m_topOfStack);

            // pop
            m_topOfStack = m_topOfStack.Parent;

            // epilog
            var epilogContext = new Context(this, m_topOfStack, Context.Scope.PrologEpilogResult);
            node.Epilog(epilogContext);

            // recycle
            var recycler = GetRecycler<Frame>();
            recycler.Recycle(frame);
        }
        private void Push(Node child) {

            // prolog
            Value substitute;
            var prologContext = new Context(this, m_topOfStack, Context.Scope.PrologEpilogResult);
            if (child.Prolog(prologContext, out substitute)) {

                // skip child if substitute is null
                if (substitute.IsNull)
                    return;

                // substitute child
                child = new Node(Loader, substitute);
            }

            // initialize frame & push
            m_topOfStack = NewFrame(m_topOfStack, child);

            // push auxiliary stacks
            var privateStacks = (Type[])child.AuxiliaryStacks();
            if (privateStacks != null) {
                for (int i = 0; i < privateStacks.Length; i++)
                    PushAuxiliary(privateStacks[i]);
            }
        }

        // traversal
        private bool YieldResult(Node leaf, out Value result) {
            result = leaf.Value;

            // substitute result; if substitute is null then skip result
            Value substitute;
            var context = new Context(this, m_topOfStack, Context.Scope.PrologEpilogResult);
            if (leaf.Result(context, leaf.Value, out substitute))
                result = substitute;

            // the only way to return null is via Info.NullResult
            if (result.IsReference && result.Object == Info.NullResult) {
                result = default(Value);
                return true;
            }

            // skip the result if it is null
            return !result.IsNull;
        }
        private bool StackEmpty {
            get { return m_topOfStack == m_bottomOfStack; }
        }
        private IEnumerable<Value> Traverse() {
            
            // create root frame and link it to the parent frame
            m_topOfStack = NewFrame(m_bottomOfStack, Node.GetDummyNode(m_root));

            // traverse tree 
            while (!StackEmpty) {

                // while there are children
                while (true) {

                    var moreChildren = m_topOfStack.MoveNext();

                    // finished enumerating children
                    if (!moreChildren) {
                        Pop();
                        break;
                    }

                    // get current child
                    var child = m_topOfStack.Current;

                    // internal node
                    if (child.IsInternalNode) {
                        Push(child);
                        break;
                    }

                    // yield a result (leaf node)
                    Value result;
                    if (YieldResult(child, out result))
                        yield return result;
                }
            }

            Dispose();
        }

        // identity
        internal Frame TopOfStack {
            get { return m_topOfStack; }
        }
        internal Loader Loader {
            get { return m_evaluator.Loader; }
        }

        // continuations
        internal void DisposeContinuation() {
            if (m_continuation == null)
                return;

            m_continuation.Dispose();
            m_continuation = null;
        }
        internal Evaluation Continue(Value value) {
            DisposeContinuation();

            if (m_isDisposed)
                throw new InvalidOperationException(
                    "Cannot continue after being disposed.");

            // activate continuation
            m_continuation = new Evaluation(this, value);

            return m_continuation;
        }
        internal bool HasContinuation {
            get { return m_continuation != null; }
        }

        // local
        internal void SetLocal(Frame frame, object frameLocal) {

            // create local for this evaluation (and cloned inherited locals)
            if (m_localsByFrame == null)
                m_localsByFrame = new Dictionary<Frame, object>();

            m_localsByFrame[frame] = frameLocal;
        }
        internal object TryGetLocal(Frame frame) {

            // hit cache
            var local = m_localsByFrame != null ?
                m_localsByFrame.GetValueOrDefault(frame) : null;

            // cache hit!
            if (local != null)
                return local;

            // hit inherited cache
            local = m_evaluator.TryGetLocal(frame);
            if (local != null) {

                // clone inherited local
                var cloneable = local as ICloneable;
                if (cloneable != null) 
                    local = cloneable.Clone();

                // create local for cloned inherited locals (and this evaluation)
                if (m_localsByFrame == null)
                    m_localsByFrame = new Dictionary<Frame, object>();

                // cache inherited cloned local
                return m_localsByFrame[frame] = local;
            }

            // no local for this frame
            return null;
        }
        internal AuxiliaryFrame TryGetTopOfAuxiliaryStack(Type type) {

            // create cache of private stacks roots for this evaluation
            if (m_topOfAuxiliaryStacks == null)
                m_topOfAuxiliaryStacks = new Dictionary<Type, AuxiliaryFrame>();

            // hit cache
            var topOfAuxiliaryStack = m_topOfAuxiliaryStacks.GetValueOrDefault(type);
            if (topOfAuxiliaryStack != null)
                return topOfAuxiliaryStack;

            // hit inherited cache
            topOfAuxiliaryStack = m_evaluator.GetTopOfAuxiliaryStack(type);
            if (topOfAuxiliaryStack != null) {

                // cache top of private stack
                return m_topOfAuxiliaryStacks[type] = topOfAuxiliaryStack;
            }

            // no private stack found
            return null;
        }

        // recycler
        internal Recycler<T> GetRecycler<T>() where T : IRecyclable, new() {
            return m_evaluator.GetRecycler<T>();
        }

        // enumerator (see boilerplate)
        public bool MoveNext() {
            return m_traversal.MoveNext();
        }
        public Value Current {
            get { return m_traversal.Current; }
        }
        public void Dispose() {
            DisposeContinuation();

            if (m_continuation != null)
                m_continuation.m_continuation = null;

            m_traversal.Dispose();

            while (!StackEmpty)
                Pop();

            m_isDisposed = true;
        }
        public void Reset() {
            if (m_isDisposed)
                throw new InvalidOperationException(
                    "Cannot reset after being disposed.");

            if (m_isContinuation)
                throw new InvalidOperationException(
                    "Cannot reset a continuation.");

            DisposeContinuation();

            m_topOfStack = null;
            m_topOfAuxiliaryStacks = null;
            m_localsByFrame = null;

            // initialize the traversal
            m_traversal = Traverse().GetEnumerator();
        }
    }
    internal sealed class Evaluator : IEnumerable<Value> {

        // identity
        private readonly Loader m_loader;
        private readonly Value m_root;
        private readonly bool m_isAsynchronous;
        private readonly Evaluation m_parentEvaluation;

        // if asynchronous then these are clones of the auxiliary stacks & local
        private readonly Dictionary<Type, AuxiliaryFrame> m_auxiliaryParentFrames;
        private readonly Dictionary<Frame, object> m_frameLocals;

        // recyclers (inherited if synchronous, new if asynchronous)
        private Recycler<Frame> m_frameRecycler;
        private Recycler<AuxiliaryFrame> m_privateFrameRecycler;

        // continued
        private IEnumerator<Value> m_enumerator;

        internal Evaluator(
            Loader loader,
            Value root,
            Evaluation parentEvaluation,
            bool isAsynchronous) {

            m_loader = loader;
            m_root = root;
            m_parentEvaluation = parentEvaluation;
            m_isAsynchronous = isAsynchronous;

            if (m_isAsynchronous) {

                // initialize m_localByFrame
                m_frameLocals = null;
                m_auxiliaryParentFrames = null;
                throw new NotImplementedException();
            }
        }

        private Recycler<T> ActivateRecycler<T>() where T : IRecyclable, new() {

            // activate frame recycler
            if (m_parentEvaluation == null || m_isAsynchronous)
                return new Recycler<T>();

            // inherit frame recycler
            return m_parentEvaluation.GetRecycler<T>();
        }

        internal Loader Loader {
            get { return m_loader; }
        }
        internal Value Root {
            get { return m_root; }
        }
        internal AuxiliaryFrame GetTopOfAuxiliaryStack(Type type) {
            AuxiliaryFrame topOfAuxiliaryStack = null;

            // if not asynchronous than try inherit
            if (!m_isAsynchronous) {
                if (m_parentEvaluation != null)
                    topOfAuxiliaryStack = m_parentEvaluation.TryGetTopOfAuxiliaryStack(type);

            // if asynchronous than try cloned cache
            } else if (m_auxiliaryParentFrames != null) {
                topOfAuxiliaryStack = m_auxiliaryParentFrames.GetValueOrDefault(type);
            }

            // no private stack
            if (topOfAuxiliaryStack == null)
                return null;

            return topOfAuxiliaryStack;
        }
        internal object TryGetLocal(Frame frame) {
            object local = null;

            // if not asynchronous than try inherit
            if (!m_isAsynchronous) {
                if (m_parentEvaluation != null)
                    local = m_parentEvaluation.TryGetLocal(frame);

            // if asynchronous than try cloned cache
            } else if (m_frameLocals != null) {
                local = m_frameLocals.GetValueOrDefault(frame);
            }

            // no local found
            if (local == null)
                return null;

            return local;
        }
        internal Recycler<T> GetRecycler<T>() where T : IRecyclable, new() {

            // frames
            if (typeof(T) == typeof(Frame)) {
                if (m_frameRecycler == null)
                    m_frameRecycler = ActivateRecycler<Frame>();
                return (Recycler<T>)(object)m_frameRecycler;

            // private frames
            } else if (typeof(T) == typeof(AuxiliaryFrame)) {
                if (m_privateFrameRecycler == null)
                    m_privateFrameRecycler = ActivateRecycler<AuxiliaryFrame>();
                return (Recycler<T>)(object)m_privateFrameRecycler;
            }

            throw new NotSupportedException();
        }
        internal Frame TopOfStack {
            get {
                if (m_parentEvaluation == null)
                    return null;

                return m_parentEvaluation.TopOfStack; 
            }
        }

        public IEnumerator<Value> GetEnumerator() {
            return m_enumerator = new Evaluation(this);
        }
        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }
    }
}

